
#include <iostream>
#include <fstream>
#include "lklist.h"

using namespace std;

typedef int elemtype;
typedef lklisttpl<elemtype> lklist;

lklist *merge( lklist *, lklist * );

int main()
{
    ifstream in("in.txt");
    vector<elemtype> va, vb;
    lklist *ha, *hb, *hc;
    int i, n;
    int t;

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	va.push_back(t);
    }

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	vb.push_back(t);
    }

    ha = createlk<lklist,elemtype>( va, WITHHEAD );
    hb = createlk<lklist,elemtype>( vb, WITHHEAD );

    printlk( ha, WITHHEAD ); cout << endl;
    printlk( hb, WITHHEAD ); cout << endl;

    hc = merge( ha, hb );
    printlk( hc, WITHHEAD ); cout << endl;

    destorylk( ha, WITHHEAD );
    destorylk( hb, WITHHEAD );
    destorylk( hc, WITHHEAD );

    return 0;
}

/* ******************************************************
 *             Answer to this question.
 * ******************************************************/

lklist *merge( lklist *ha, lklist *hb )
{
    lklist **pa, **pb, *hc;
    
    hc = new lklist;
    pa = &ha->next;
    pb = &hb->next;
    while( *pa && *pb ){
        pa = &(*pa)->next;
        pb = &(*pb)->next;
    }
    if( !*pa ){
	*pa = hb->next;
	hb->next = NULL;
	hc->next = ha->next;
	ha->next = NULL;
    }
    else{
	*pb = ha->next;
	ha->next = NULL;
	hc->next = hb->next;
	hb->next = NULL;
    }
    
    return hc;
}
